use std::collections::HashMap;
use std::mem::swap;

// No clone, no copy! That asserts that an LRUHandle exists only once.
/// struct LRUHandle<T>(*mut LRUNode<T>); 是一个 Rust 结构体，用于封装指向 LRU 缓存中节点的原始指针，充当访问或操作特定节点的 "句柄"（handle）。
///
/// 核心作用：
///
/// 标识特定节点：通过存储指向 LRUNode<T> 节点的原始指针（*mut LRUNode<T>），LRUHandle<T> 可以唯一标识 LRU 链表中的一个具体节点。
///
/// 提供操作入口：在 LRU 缓存的实现中，当需要对某个节点执行操作（如移动到尾部标记为 "最近使用"、删除节点等）时，可通过这个句柄快速定位到目标节点，而无需从头遍历链表。
///
/// 抽象指针细节：将原始指针封装在结构体中，避免直接暴露裸指针，一定程度上简化了外部使用，同时保留了直接操作节点的灵活性。
///
/// 使用场景：
///
/// 当调用 insert 方法向 LRU 缓存添加元素时，通常会返回一个 LRUHandle<T>（如你之前提供的 insert 方法的返回值），用于后续操作该元素。
///
/// 通过句柄可以快速找到对应的节点，执行如 mark_as_recently_used 等操作，这在 LRU 缓存的核心逻辑中非常重要。
struct LRUHandle<T>(*mut LRUNode<T>);

/// 这个 LRUNode 结构体是LRU（最近最少使用）缓存机制中双向链表的节点结构，用于存储数据并维护节点之间的前后关联关系，是实现 LRU 淘汰策略的基础数据结构。
struct LRUNode<T> {
    /// 指向后一个节点的所有权指针（Box 表示独占所有权），None 表示当前节点是链表尾。
    next: Option<Box<LRUNode<T>>>, // None in the list's last node
    /// 指向前一个节点的原始指针（非所有权，仅用于反向遍历），None 表示当前节点是链表头。
    prev: Option<*mut LRUNode<T>>,
    /// 存储节点的数据（T 类型）。特殊约定：None 通常表示该节点是链表的 “哨兵头节点”（不存储实际数据，仅用于简化链表操作）。
    data: Option<T>, // if None, then we have reached the head node
}

/// 这个 LRUList<T> 结构体是LRU（最近最少使用）缓存机制中的双向链表容器，用于管理所有缓存节点的访问顺序。
/// 它通过维护一个带头节点的双向链表，记录数据的访问历史，是实现 “淘汰最久未使用数据” 策略的核心组件。
///
/// 在 Cache 里面的这个 LRUList 里面存放的是 key
struct LRUList<T> {
    /// 链表的哨兵头节点（通常 data 字段为 None），不存储实际数据，仅作为链表的固定起点，简化边界操作。
    head: LRUNode<T>,
    /// 链表中实际存储数据的节点数量（不包含哨兵头节点），用于快速判断缓存是否达到容量上限。
    count: usize,
}

/// This is likely unstable; more investigation is needed into correct behavior!
impl<T> LRUList<T> {
    fn new() -> LRUList<T> {
        LRUList {
            head: LRUNode {
                data: None,
                next: None,
                prev: None,
            },
            count: 0,
        }
    }

    /// Inserts new element at front (least recently used element)
    ///
    /// 这段代码是 LRU（最近最少使用）缓存中向头部插入新元素的方法，涉及双向链表节点的指针（prev 和 next）操作。
    /// 核心逻辑是将新元素插入到链表头部（作为最不常用元素），下面详细解析指针的变化过程：
    ///
    /// 情况 1：链表非空（已有其他节点，self.head.next.is_some()）
    ///
    /// 此时链表结构初始为：head <-> node1 <-> node2 ...（head.next 指向 node1，node1.prev 指向 head）
    ///
    /// 1.创建新节点 new：
    ///
    /// - new.prev 初始化为 Some(&mut self.head as *mut _)（指向头节点）
    ///
    /// - new.next 初始化为 None
    ///
    /// 2.保存新节点的原始指针 newp：
    ///
    /// - let newp = new.as_mut() as *mut LRUNode<T>（后续用于更新其他节点的指针）
    ///
    /// 3.更新原头节点后第一个节点（node1）的 prev 指针：
    ///
    /// - self.head.next.as_mut().unwrap().prev = Some(newp)→ 让 node1 的前指针指向新节点 new
    ///
    /// 4.调整头节点与新节点的 next 指针：
    ///
    /// - new.next = self.head.next.take()：将原头节点的 next（即 node1）转移给新节点的 next
    ///
    /// - self.head.next = Some(new)：头节点的 next 改为指向新节点
    ///
    /// - 此时链表变为：head <-> new <-> node1 <-> node2 ...
    ///
    /// 情况 2：链表为空（首次插入，self.head.next.is_none()）
    ///
    /// 此时链表只有头节点，head.next 和 head.prev 均为 None。
    ///
    /// 1.创建新节点 new：
    ///
    /// - new.prev 初始化为 Some(&mut self.head as *mut _)（指向头节点）
    ///
    /// - new.next 初始化为 None
    ///
    /// 2.保存新节点的原始指针 newp：
    ///
    /// - let newp = new.as_mut() as *mut LRUNode<T>
    ///
    /// 3.更新头节点的 prev 指针（指向新节点，因为新节点也是尾节点）：
    ///
    /// - self.head.prev = Some(newp)
    ///
    /// 4.更新头节点的 next 指针（指向新节点，作为第一个元素）：
    ///
    /// - self.head.next = Some(new)
    ///
    /// 此时链表变为：head <-> new（新节点既是第一个元素，也是最后一个元素）
    ///
    /// 最终返回值
    ///
    /// 无论哪种情况，都会返回 LRUHandle(newp)，其中 newp 是新节点的原始指针，用于后续操作（如访问、移动节点等）。
    fn insert(&mut self, elem: T) -> LRUHandle<T> {
        self.count += 1;
        // Not first element
        if self.head.next.is_some() {
            let mut new = Box::new(LRUNode {
                data: Some(elem),
                next: None,
                prev: Some(&mut self.head as *mut LRUNode<T>),
            });
            let newp = new.as_mut() as *mut LRUNode<T>;

            // Set up the node after the new one
            self.head.next.as_mut().unwrap().prev = Some(newp);
            // Replace head.next with None and set the new node's next to that
            new.next = self.head.next.take();
            self.head.next = Some(new);

            LRUHandle(newp)
        } else {
            // First node; the only node right now is an empty head node
            let mut new = Box::new(LRUNode {
                data: Some(elem),
                next: None,
                prev: Some(&mut self.head as *mut LRUNode<T>),
            });
            let newp = new.as_mut() as *mut LRUNode<T>;

            // Set tail
            self.head.prev = Some(newp);
            // Set first node
            self.head.next = Some(new);

            LRUHandle(newp)
        }
    }

    /// 这段代码是 LRU（最近最少使用）缓存中的 remove_last 方法，用于移除链表中最后一个节点（即最近最常使用的元素，
    /// 因为 LRU 通常将最近访问的元素移到尾部），并返回该节点中存储的数据。
    fn remove_last(&mut self) -> Option<T> {
        // 首先检查缓存中元素数量（self.count()）是否为 0，如果为空则直接返回 None
        if self.count() == 0 {
            return None;
        }
        // 通过复杂的指针操作 (*((*self.head.prev.unwrap()).prev.unwrap())).next.take() 获取最后一个节点的所有权
        // 拆解来看：
        // self.head.prev 指向尾节点（最后一个节点）
        // (*self.head.prev.unwrap()).prev 指向尾节点的前一个节点（倒数第二个节点）
        // 对倒数第二个节点调用 next.take() 会取出其 next 指针（即尾节点）并将其设为 None，从而将尾节点从链表中拆下来
        let mut lasto = unsafe { (*((*self.head.prev.unwrap()).prev.unwrap())).next.take() };
        // 断言确保成功获取到了最后一个节点（lasto.is_some()）
        assert!(lasto.is_some());
        if let Some(ref mut last) = lasto {
            assert!(last.prev.is_some());
            assert!(self.head.prev.is_some());
            // 将头节点的 prev 指针更新为最后一个节点的 prev（即指向原倒数第二个节点，使其成为新的尾节点）
            // 减少缓存元素计数（self.count -= 1）
            self.head.prev = last.prev;
            self.count -= 1;
            // 通过 last.data.take() 取出节点中存储的数据并返回（同时清空节点中的数据）
            last.data.take()
        } else {
            None
        }
    }

    /// 删除 node_handle 节点
    ///```
    ///      _____________________________
    ///     /                             \
    /// --prev---------node_handle--------next--------
    ///     \_____________________________/
    ///```
    ///
    fn remove(&mut self, node_handle: LRUHandle<T>) -> T {
        unsafe {
            let d = (*node_handle.0).data.take().unwrap();
            // Take ownership of node to be removed.
            let mut current = (*(*node_handle.0).prev.unwrap()).next.take().unwrap();
            let prev = current.prev.unwrap();
            // Update previous node's successor.
            if current.next.is_some() {
                // Update next node's predecessor.
                current.next.as_mut().unwrap().prev = current.prev.take();
            }
            (*prev).next = current.next.take();

            self.count -= 1;

            d
        }
    }

    /// Reinserts the referenced node at the front.
    ///
    /// 这个 reinsert_front 方法是 LRU（最近最少使用）缓存机制中维护链表节点顺序的核心操作，用于将指定节点（node_handle）移动到链表头部，标记为 “最近被访问”，从而保证 LRU 策略能正确淘汰最久未使用的节点。
    ///
    /// reinsert_front 的核心功能是维护 LRU 链表的访问顺序：
    ///
    /// 每次访问缓存节点时，通过该方法将节点移到链表头部，标记为 “最近使用”；
    ///
    /// 间接影响缓存淘汰策略：当缓存满时，链表尾部（最久未使用）的节点会被优先删除；
    ///
    /// 通过直接操作指针实现高效移动，避免链表节点的内存拷贝，保证缓存操作的性能
    fn reinsert_front(&mut self, node_handle: &LRUHandle<T>) {
        unsafe {
            // 获取当前节点的前序节点
            // node_handle.0 是指向当前节点的原始指针；
            // prevp 是当前节点的前一个节点（前驱）的指针。
            let prevp = (*node_handle.0).prev.unwrap();
            // 目的是从原位置移除当前节点：让当前节点的后序节点（或链表头）与当前节点的前序节点直接相连，跳过当前节点。
            // If not last node, update following node's prev
            // 如果当前节点不是最后一个节点，更新后序节点的前驱指针
            if let Some(next) = (*node_handle.0).next.as_mut() {
                next.prev = Some(prevp);
            } else {
                // If last node, update head
                // 如果当前节点是最后一个节点，更新链表头的前驱指针（指向新的尾节点）
                self.head.prev = Some(prevp);
            }
            // 通过两次 swap 操作调整指针指向，将当前节点从原位置 “摘出”，并连接到链表头的后面。
            // Swap this.next with prev.next. After that, this.next refers to this (!)
            // 交换当前节点的前序节点的 next 与当前节点的 next（断开原连接）
            swap(&mut (*prevp).next, &mut (*node_handle.0).next);
            // To reinsert at head, swap head's next with this.next
            // 交换当前节点的 next 与链表头的 next（准备插入头部）
            swap(&mut (*node_handle.0).next, &mut self.head.next);
            // Update this' prev reference to point to head.

            // Update the second node's prev reference.
            // 当前节点有新的后序节点（原头部第一个节点），更新前驱指针指向当前节点
            if let Some(ref mut newnext) = (*node_handle.0).next {
                (*node_handle.0).prev = newnext.prev;
                newnext.prev = Some(node_handle.0);
            } else {
                // Only one node, being the last one; avoid head.prev pointing to head
                // 链表中只有当前节点，让头节点的前驱指向自己（形成循环）
                self.head.prev = Some(node_handle.0);
            }

            assert!(self.head.next.is_some());
            assert!(self.head.prev.is_some());
        }
    }

    fn count(&self) -> usize {
        self.count
    }

    fn _testing_head_ref(&self) -> Option<&T> {
        if let Some(ref first) = self.head.next {
            first.data.as_ref()
        } else {
            None
        }
    }
}

pub type CacheKey = [u8; 16];
pub type CacheID = u64;
type CacheEntry<T> = (T, LRUHandle<CacheKey>);

/// Implementation of `ShardedLRUCache`.
/// Based on a HashMap; the elements are linked in order to support the LRU ordering.
///
/// 这个 Cache<T> 结构体是一个基于 LRU（最近最少使用）策略的缓存实现，用于临时存储频繁访问的数据，以减少重复计算或磁盘 I/O，提升系统性能。
/// 它通过哈希表实现快速查询，同时用 LRU 链表维护数据的访问顺序，在缓存满时自动淘汰最久未使用的条目。
pub struct Cache<T> {
    // note: CacheKeys (Vec<u8>) are duplicated between list and map. If this turns out to be a
    // performance bottleneck, another layer of indirection™ can solve this by mapping the key
    // to a numeric handle that keys both list and map.
    /// LRU 双向链表，记录缓存键（CacheKey）的访问顺序：
    /// - 头部是 “最近使用” 的键；
    /// - 尾部是 “最久未使用” 的键，用于缓存满时淘汰。
    list: LRUList<CacheKey>,
    /// 哈希表，存储缓存键与对应值（CacheEntry<T>）的映射，支持 O (1) 时间复杂度的查询。
    map: HashMap<CacheKey, CacheEntry<T>>,
    /// 缓存的最大容量（通常指最大条目数），超过后会触发 LRU 淘汰机制。
    cap: usize,
    /// 缓存实例的唯一标识，用于区分不同的缓存（如多个表的块缓存）。
    id: u64,
}

impl<T> Cache<T> {
    pub fn new(capacity: usize) -> Cache<T> {
        assert!(capacity > 0);
        Cache {
            list: LRUList::new(),
            map: HashMap::with_capacity(1024),
            cap: capacity,
            id: 0,
        }
    }

    /// Returns an ID that is unique for this cache and that can be used to partition the cache
    /// among several users.
    pub fn new_cache_id(&mut self) -> CacheID {
        self.id += 1;
        self.id
    }

    /// How many the cache currently contains
    pub fn count(&self) -> usize {
        self.list.count()
    }

    /// The capacity of this cache
    pub fn cap(&self) -> usize {
        self.cap
    }

    /// Insert a new element into the cache. The returned `CacheHandle` can be used for further
    /// operations on that element.
    /// If the capacity has been reached, the least recently used element is removed from the
    /// cache.
    ///
    /// 这段代码定义了一个 insert 方法，用于向缓存（Cache）中插入新元素，同时实现了LRU（最近最少使用）淘汰策略，是缓存管理的核心操作之一。
    ///
    /// 这个方法的核心是维护缓存的容量限制和访问顺序：
    ///
    /// 当缓存满时，自动淘汰最久未使用的元素，为新元素腾出空间（LRU 策略）。
    ///
    /// 结合链表（self.list）和哈希表（self.map）：链表记录元素的访问顺序，哈希表提供 O (1) 时间复杂度的元素查找。
    ///
    /// 在实际应用中，这种实现广泛用于需要高效缓存管理的场景（如数据库缓存、计算结果缓存等），既能快速访问常用元素，又能自动清理不常用元素以控制内存占用。
    pub fn insert(&mut self, key: &CacheKey, elem: T) {
        // 检查缓存容量：
        // 通过 self.list.count() >= self.cap 判断当前缓存中的元素数量是否已达到容量上限（self.cap）。
        // 如果已满，需要先删除 “最近最少使用” 的元素：
        // 调用 self.list.remove_last() 移除链表中最后一个元素（LRU 策略中，链表末尾通常代表最久未使用的元素）。
        // 同时从哈希表 self.map 中删除该元素的键，确保数据一致性。
        // 若删除失败则触发 panic（通常是异常情况）。
        if self.list.count() >= self.cap {
            if let Some(removed_key) = self.list.remove_last() {
                assert!(self.map.remove(&removed_key).is_some());
            } else {
                panic!("could not remove_last(); bug!");
            }
        }
        // 插入新元素：
        // 调用 self.list.insert(*key) 在链表中插入新元素的键，并获取一个链表句柄（lru_handle），用于跟踪元素的访问顺序。
        // 将新元素（elem）和链表句柄一起存入哈希表 self.map 中，键为缓存键（*key），值为元素和其在链表中的位置信息。
        let lru_handle = self.list.insert(*key);
        self.map.insert(*key, (elem, lru_handle));
    }

    /// Retrieve an element from the cache.
    /// If the element has been preempted from the cache in the meantime, this returns None.
    ///
    /// 这个 get 方法是缓存（Cache）的查询接口，用于根据键（CacheKey）从缓存中获取对应的值，并更新该缓存项的访问热度（通过 LRU 算法），是缓存机制中实现 “最近最少使用淘汰策略” 的核心操作之一。
    pub fn get<'a>(&'a mut self, key: &CacheKey) -> Option<&'a T> {
        match self.map.get(key) {
            None => None,  // 键不存在，返回 None
            Some((elem, lru_handle)) => {
                // 键存在，执行后续操作
                self.list.reinsert_front(lru_handle);
                Some(elem)
            }
        }
    }

    /// Remove an element from the cache (for invalidation).
    pub fn remove(&mut self, key: &CacheKey) -> Option<T> {
        match self.map.remove(key) {
            None => None,
            Some((elem, lru_handle)) => {
                self.list.remove(lru_handle);
                Some(elem)
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::LRUList;
    use super::*;

    fn make_key(a: u8, b: u8, c: u8) -> CacheKey {
        [a, b, c, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    }

    #[test]
    fn test_blockcache_cache_add_rm() {
        let mut cache = Cache::new(128);

        let h_123 = make_key(1, 2, 3);
        let h_521 = make_key(1, 2, 4);
        let h_372 = make_key(3, 4, 5);
        let h_332 = make_key(6, 3, 1);
        let h_899 = make_key(8, 2, 1);

        cache.insert(&h_123, 123);
        cache.insert(&h_332, 332);
        cache.insert(&h_521, 521);
        cache.insert(&h_372, 372);
        cache.insert(&h_899, 899);

        assert_eq!(cache.count(), 5);

        assert_eq!(cache.get(&h_123), Some(&123));
        assert_eq!(cache.get(&h_372), Some(&372));

        assert_eq!(cache.remove(&h_521), Some(521));
        assert_eq!(cache.get(&h_521), None);
        assert_eq!(cache.remove(&h_521), None);

        assert_eq!(cache.count(), 4);
    }

    #[test]
    fn test_blockcache_cache_capacity() {
        let mut cache = Cache::new(3);

        let h_123 = make_key(1, 2, 3);
        let h_521 = make_key(1, 2, 4);
        let h_372 = make_key(3, 4, 5);
        let h_332 = make_key(6, 3, 1);
        let h_899 = make_key(8, 2, 1);

        cache.insert(&h_123, 123);
        cache.insert(&h_332, 332);
        cache.insert(&h_521, 521);
        cache.insert(&h_372, 372);
        cache.insert(&h_899, 899);

        assert_eq!(cache.count(), 3);

        assert_eq!(cache.get(&h_123), None);
        assert_eq!(cache.get(&h_332), None);
        assert_eq!(cache.get(&h_521), Some(&521));
        assert_eq!(cache.get(&h_372), Some(&372));
        assert_eq!(cache.get(&h_899), Some(&899));
    }

    #[test]
    fn test_blockcache_lru_remove() {
        let mut lru = LRUList::<usize>::new();

        let h_56 = lru.insert(56);
        lru.insert(22);
        lru.insert(223);
        let h_244 = lru.insert(244);
        lru.insert(1111);
        let h_12 = lru.insert(12);

        assert_eq!(lru.count(), 6);
        assert_eq!(244, lru.remove(h_244));
        assert_eq!(lru.count(), 5);
        assert_eq!(12, lru.remove(h_12));
        assert_eq!(lru.count(), 4);
        assert_eq!(56, lru.remove(h_56));
        assert_eq!(lru.count(), 3);
    }

    #[test]
    fn test_blockcache_lru_1() {
        let mut lru = LRUList::<usize>::new();

        lru.insert(56);
        lru.insert(22);
        lru.insert(244);
        lru.insert(12);

        assert_eq!(lru.count(), 4);

        assert_eq!(Some(56), lru.remove_last());
        assert_eq!(Some(22), lru.remove_last());
        assert_eq!(Some(244), lru.remove_last());

        assert_eq!(lru.count(), 1);

        assert_eq!(Some(12), lru.remove_last());

        assert_eq!(lru.count(), 0);

        assert_eq!(None, lru.remove_last());
    }

    #[test]
    fn test_blockcache_lru_reinsert() {
        let mut lru = LRUList::<usize>::new();

        let handle1 = lru.insert(56);
        let handle2 = lru.insert(22);
        let handle3 = lru.insert(244);

        assert_eq!(lru._testing_head_ref().copied().unwrap(), 244);

        lru.reinsert_front(&handle1);

        assert_eq!(lru._testing_head_ref().copied().unwrap(), 56);

        lru.reinsert_front(&handle3);

        assert_eq!(lru._testing_head_ref().copied().unwrap(), 244);

        lru.reinsert_front(&handle2);

        assert_eq!(lru._testing_head_ref().copied().unwrap(), 22);

        assert_eq!(lru.remove_last(), Some(56));
        assert_eq!(lru.remove_last(), Some(244));
        assert_eq!(lru.remove_last(), Some(22));
    }

    #[test]
    fn test_blockcache_lru_reinsert_2() {
        let mut lru = LRUList::<usize>::new();

        let handles = [
            lru.insert(0),
            lru.insert(1),
            lru.insert(2),
            lru.insert(3),
            lru.insert(4),
            lru.insert(5),
            lru.insert(6),
            lru.insert(7),
            lru.insert(8),
        ];

        (0..9).for_each(|i| {
            lru.reinsert_front(&handles[i]);
            assert_eq!(lru._testing_head_ref().copied(), Some(i));
        });
    }

    #[test]
    fn test_blockcache_lru_edge_cases() {
        let mut lru = LRUList::<usize>::new();

        let handle = lru.insert(3);

        lru.reinsert_front(&handle);
        assert_eq!(lru._testing_head_ref().copied(), Some(3));
        assert_eq!(lru.remove_last(), Some(3));
        assert_eq!(lru.remove_last(), None);
        assert_eq!(lru.remove_last(), None);
    }
}
